#include <bits/stdc++.h>
using namespace std;

#define MAXV 100    // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大

// 邻接矩阵存储结构
typedef struct {
    int edges[MAXV][MAXV];  // 邻接矩阵
    int n, e;               // 顶点数和边数
} MatGraph;

// 邻接表的边节点
typedef struct ArcNode {
    int adjvex;             // 邻接点
    int weight;             // 边的权值
    struct ArcNode *nextarc;// 下一条边
} ArcNode;
// 邻接表的头结点
typedef struct VNode {
    ArcNode *firstarc;      // 指向第一条边
} VNode;
// 邻接表
typedef struct {
    VNode adjlist[MAXV];    // 邻接表
    int n, e;               // 顶点数和边数
} AdjGraph;  // 两个名称表示同一结构，适应原函数参数

// 邻接矩阵转换为邻接表
void Mat2List(MatGraph &g, AdjGraph* &G) {
    int i, j;
    ArcNode *p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    // 初始化头结点数组
    for(i = 0; i < g.n; i++) {
        G->adjlist[i].firstarc = NULL;
    }

    for(i = 0; i < g.n; i++) {
        for(j = g.n-1; j >= 0; j--) {
            if(g.edges[i][j] != 0 && g.edges[i][j] != INF) {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j; // 邻接点
                p->weight = g.edges[i][j];

                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }
    G->n = g.n; 
    G->e = g.e;
}
// 邻接表转换为邻接矩阵
void List2Matrix(AdjGraph *G, MatGraph &g) { 
    int i, j;
    ArcNode *p;

    // 初始化邻接矩阵
    for(i = 0; i < G->n; i++) {
        for(j = 0; j < G->n; j++) {
            if(i == j) g.edges[i][j] = 0;
            else g.edges[i][j] = INF;
        }
    }

    for(i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        while(p != NULL) {
            g.edges[i][p->adjvex] = p->weight;
            p = p->nextarc;
        }
    }
    g.n = G->n; 
    g.e = G->e;
}

// 辅助函数：打印邻接矩阵
void printMatGraph(MatGraph g) {
    cout << "邻接矩阵:" << endl;
    for(int i = 0; i < g.n; i++) {
        for(int j = 0; j < g.n; j++) {
            if(g.edges[i][j] == INF)
                cout << "INF\t";
            else
                cout << g.edges[i][j] << "\t";
        }
        cout << endl;
    }
}

// 辅助函数：打印邻接表
void printAdjGraph(AdjGraph *G) {
    cout << "邻接表:" << endl;
    for(int i = 0; i < G->n; i++) {
        cout << "顶点" << i << ": ";
        ArcNode *p = G->adjlist[i].firstarc;
        while(p != NULL) {
            cout << "(" << p->adjvex << "," << p->weight << ") ";
            p = p->nextarc;
        }
        cout << endl;
    }
}

// 测试用例1：无向图
void testCase1() {
    cout << "\n=== 测试用例1：无向图 ===" << endl;
    MatGraph matG;
    matG.n = 4;  // 4个顶点
    matG.e = 4;  // 4条边
    
    // 初始化邻接矩阵
    for(int i = 0; i < matG.n; i++) {
        for(int j = 0; j < matG.n; j++) {
            if(i == j) matG.edges[i][j] = 0;
            else matG.edges[i][j] = INF;
        }
    }
    
    // 添加边 (无向图对称)
    matG.edges[0][1] = matG.edges[1][0] = 2;
    matG.edges[0][2] = matG.edges[2][0] = 5;
    matG.edges[1][2] = matG.edges[2][1] = 1;
    matG.edges[2][3] = matG.edges[3][2] = 3;
    
    cout << "原始邻接矩阵:" << endl;
    printMatGraph(matG);
    
    // 转换为邻接表
    AdjGraph *adjG;
    Mat2List(matG, adjG);
    cout << "\n转换后的邻接表:" << endl;
    printAdjGraph(adjG);
    
    // 转换回邻接矩阵，验证正确性
    MatGraph matG2;
    List2Matrix(adjG, matG2);
    cout << "\n从邻接表转换回的邻接矩阵:" << endl;
    printMatGraph(matG2);
}

// 测试用例2：有向图
void testCase2() {
    cout << "\n=== 测试用例2：有向图 ===" << endl;
    MatGraph matG;
    matG.n = 3;  // 3个顶点
    matG.e = 3;  // 3条边
    
    // 初始化邻接矩阵
    for(int i = 0; i < matG.n; i++) {
        for(int j = 0; j < matG.n; j++) {
            if(i == j) matG.edges[i][j] = 0;
            else matG.edges[i][j] = INF;
        }
    }
    
    // 添加有向边
    matG.edges[0][1] = 10;
    matG.edges[1][2] = 20;
    matG.edges[2][0] = 30;
    
    cout << "原始邻接矩阵:" << endl;
    printMatGraph(matG);
    
    // 转换为邻接表
    AdjGraph *adjG;
    Mat2List(matG, adjG);
    cout << "\n转换后的邻接表:" << endl;
    printAdjGraph(adjG);
    
    // 转换回邻接矩阵，验证正确性
    MatGraph matG2;
    List2Matrix(adjG, matG2);
    cout << "\n从邻接表转换回的邻接矩阵:" << endl;
    printMatGraph(matG2);
}

// 测试用例3：含孤立顶点的图
void testCase3() {
    cout << "\n=== 测试用例3：含孤立顶点的图 ===" << endl;
    MatGraph matG;
    matG.n = 5;  // 5个顶点
    matG.e = 2;  // 2条边
    
    // 初始化邻接矩阵
    for(int i = 0; i < matG.n; i++) {
        for(int j = 0; j < matG.n; j++) {
            if(i == j) matG.edges[i][j] = 0;
            else matG.edges[i][j] = INF;
        }
    }
    
    // 添加边
    matG.edges[0][1] = matG.edges[1][0] = 5;
    matG.edges[3][4] = matG.edges[4][3] = 8;
    // 顶点2是孤立顶点
    
    cout << "原始邻接矩阵:" << endl;
    printMatGraph(matG);
    
    // 转换为邻接表
    AdjGraph *adjG;
    Mat2List(matG, adjG);
    cout << "\n转换后的邻接表:" << endl;
    printAdjGraph(adjG);
}

int main() {
    testCase1();  // 测试无向图转换
    testCase2();  // 测试有向图转换
    testCase3();  // 测试含孤立顶点的图
    
    return 0;
}